package com.sunqianhu.algorithm.sort;

import java.util.LinkedList;
import java.util.Queue;

public class RadixSort {
    /**
     * 基数排序主函数
     * @param arr 要排序的数组
     */
    public static void sort(int[] arr) {
        int max = getMax(arr); //得到最大数
        int maxDigits = getMaxDigits(max); //得到最大数的位数

        // 使用队列数组作为“桶”
        Queue<Integer>[] buckets = new Queue[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new LinkedList<>();
        }
        //每一位
        for (int digitPos = 1; digitPos <= maxDigits; digitPos++) {
            distribute(arr, buckets, digitPos); //分配
            collect(arr, buckets);
        }
    }

    /**
     * 获取数组中的最大值
     * @param arr 数组
     * @return 最大值
     */
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    /**
     * 获取最大值的位数
     * @param number 数字
     * @return 位数
     */
    private static int getMaxDigits(int number) {
        return String.valueOf(number).length();
    }

    /**
     * 分配阶段：根据当前位上的数字将元素放入对应的桶中
     * @param arr 数组
     * @param buckets 桶数组
     * @param digitPos 当前位数（从1开始）
     */
    private static void distribute(int[] arr, Queue<Integer>[] buckets, int digitPos) {
        for (int num : arr) {
            int digit = getDigit(num, digitPos);
            buckets[digit].add(num);
        }
    }

    /**
     * 收集阶段：将桶中的元素按顺序放回原数组
     * @param arr 数组
     * @param buckets 桶数组
     */
    private static void collect(int[] arr, Queue<Integer>[] buckets) {
        int index = 0;
        for (Queue<Integer> bucket : buckets) {
            while (!bucket.isEmpty()) {
                arr[index++] = bucket.poll();
            }
        }
    }

    /**
     * 获取数字在特定位置上的数字
     * @param number 数字
     * @param position 位数位置（从1开始）
     * @return 特定位上的数字
     */
    private static int getDigit(int number, int position) {
        return (int) ((number / Math.pow(10, position - 1)) % 10);
    }

    /**
     * 打印数组的方法
     * @param arr 要打印的数组
     */
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.println("原数组:");
        printArray(arr);

        sort(arr);

        System.out.println("排序后数组:");
        printArray(arr);
    }
}
